package leetcode

// validPath 判断图中是否存在从 target 到 destination 的路径。
// 参数:
//
//	n - 图中节点的数量。
//	edges - 图中的边，每个边由一对节点组成。
//	target - 路径的起始节点。
//	destination - 路径的目标节点。
//
// 返回值:
//
//	如果存在从 target 到 destination 的路径，返回 true；否则返回 false。
func validPath(n int, edges [][]int, source int, destination int) bool {
	// 如果起始节点和目标节点相同，直接返回 true
	if source == destination {
		return true
	}

	// 边界条件检查
	if n <= 0 || (source != destination && n == 1) {
		return false
	}

	// 构建图
	graph := make([][]int, n)
	for i := range edges {
		// 检查边的节点值是否有效
		if len(edges[i]) != 2 || edges[i][0] >= n || edges[i][1] >= n {
			panic("Invalid edge values")
		}
		point1 := edges[i][0]
		point2 := edges[i][1]
		// 构建无向图
		graph[point1] = append(graph[point1], point2)
		graph[point2] = append(graph[point2], point1)
	}

	// 使用广度优先搜索
	var queue []int
	queue = append(queue, source)
	visited := make([]bool, n)
	visited[source] = true

	// 搜索路径
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]

		// 遍历当前节点的所有相邻节点
		for _, connection := range graph[cur] {
			// 如果找到目标节点，返回 true
			if connection == destination {
				return true
			}

			// 如果相邻节点未被访问，则加入队列并标记为已访问
			if !visited[connection] {
				visited[connection] = true
				queue = append(queue, connection)
			}
		}
	}

	// 如果队列为空，说明没有找到路径，返回 false
	return false
}
